package datastructure.book.dp._1_pathway.exercise.first;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _4_Solution {

    @Test
    public void test(){
        List<List<Integer>> cntList = new ArrayList<>();
        ArrayList<Integer> oneCnt = new ArrayList<>();
        oneCnt.add(2);
        ArrayList<Integer> twoCnt = new ArrayList<>();
        twoCnt.add(3);twoCnt.add(4);
        ArrayList<Integer> threeCnt = new ArrayList<>();
        threeCnt.add(6);threeCnt.add(5);threeCnt.add(7);
        ArrayList<Integer> forCnt = new ArrayList<>();
        forCnt.add(4);forCnt.add(1);forCnt.add(8);forCnt.add(3);
        cntList.add(oneCnt);cntList.add(twoCnt);cntList.add(threeCnt);cntList.add(forCnt);
        System.out.println(minimumTotal(cntList));
    }

    /**
     * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
     * 每一步只能移动到下一行中相邻的结点上。
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
     * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
     * 1 <= triangle.length <= 200
     * triangle[0].length == 1
     * triangle[i].length == triangle[i - 1].length + 1
     * -104 <= triangle[i][j] <= 104
     * 例如：
     * [2],
     * [3,4],
     * [6,5,7],
     * [4,1,8,3]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int[] f= new int[m];
        for (List<Integer> integers : triangle) {
            //只用O(m)空间复杂度，preF也可省去，每一行由后向前更新
            int preF = f[0];
            f[0] += integers.get(0);
            for (int i = 1; i < integers.size()-1; i++) {
                int curF = f[i];
                f[i] = Math.min(preF,curF)+integers.get(i);
                preF = curF;
            }
            if (integers.size() > 1) {
                f[integers.size()-1] = preF+integers.get(integers.size()-1);
            }
        }
        return arrMinNum(f);
    }

    private int arrMinNum(int[] arr){
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < result) {
                result = arr[i];
            }
        }
        return result;
    }
}
